package com.levi.stack;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.List;
import java.util.Stack;

/**
 * @author shentong
 * @date 2021/8/29 11:34
 * @Description 栈实现逆波兰表达式(后缀表达式)计算
 * 后缀表达式的概念:计算机理解的一种表达式，从左至右计算，将操作符写在运算数之后，计算的时候遍历表达式
 * 如果是数字就放入栈中，如果是运算符就从栈中弹出2个数字进行计算，把计算结果放入栈中,遍历完毕之后，栈中只会剩下一个数字，就是所求的结果
 * >>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>>
 * 思路:1.先把一个逆波兰表达式放入一个list中
 * 2.遍历list，如果是数字就放入栈中，如果是运算符就从栈中弹出2个数字进行计算，把计算结果放入栈中,遍历完毕之后，栈中只会剩下一个数字，就是所求的结果
 *FIXME 重点是中缀表达式转后缀表达式，思路在md文档中
 */
public class PolandNotation {
    public static void main(String[] args) {

        String expression = "30 4 + 5 * 6 -";

        String infixExpression = "10+((2+3)*4)-5";
        List<String> infixExpressionList = toInfixExpressionList(infixExpression);
        System.out.println(infixExpressionList);
        System.out.println("将中缀表达式list转换为后缀比到达是list:-------");
        List<String> sufixExpressionList = toSufixExpressionList(infixExpressionList);
        System.out.println(sufixExpressionList);
     /*   System.out.println("逆波兰表达式是:----------");
        List<String> list = getList(expression);
        System.out.println(list);*/
        System.out.printf("计算结果是:%d\n",calculate(sufixExpressionList));
    }

    /**
     * 把逆波兰表达式放进list中
     * @param expression
     * @return
     */
    public static List<String> getList(String expression) {
        String[] split = expression.split(" ");
        return new ArrayList<>(Arrays.asList(split));
    }

    /**
     * 遍历list，计算结果
     * @param list
     * @return
     */
    public static Integer calculate(List<String> list) {
        var stack = new Stack<String>();
        int res = 0;
        String num1 ="",num2="";
        for (String s : list) {
            if (s.matches("\\d+")) {
                stack.push(s);
            }else if (s.equals("+")){
                 num1 = stack.pop();
                 num2 = stack.pop();
                res = Integer.parseInt(num2) + Integer.parseInt(num1);
                stack.push("" + res);
            }else if (s.equals("-")){
                 num1 = stack.pop();
                 num2 = stack.pop();
                res = Integer.parseInt(num2) - Integer.parseInt(num1);
                stack.push("" + res);
            }else if (s.equals("*")){
                 num1 = stack.pop();
                 num2 = stack.pop();
                res = Integer.parseInt(num2) * Integer.parseInt(num1);
                stack.push("" + res);
            }else if (s.equals("/")){
                 num1 = stack.pop();
                 num2 = stack.pop();
                res = Integer.parseInt(num2) / Integer.parseInt(num1);
                stack.push("" + res);
            }else {
                throw new RuntimeException("数据格式不正确");
            }
        }
        return Integer.parseInt(stack.pop());
    }

    /**
     * s1 = 10+((2+3)*4)-5
     * 把一个中缀表达式字符串拆封，放到一个list中
     * @param s
     * @return list
     */
    public static List<String> toInfixExpressionList(String s) {
        List<String> list = new ArrayList<>();
        int index = 0;//遍历需要的指针
        StringBuilder str ; //用于多位数的拼接
        char c;
        while (index < s.length()) {
//            c = s.charAt(index);
            //判断如果是操作符
            if ((c=s.charAt(index)) < 48 || (c=s.charAt(index)) > 57) {
                list.add(c+"");
                index++;
            }else{
                str = new StringBuilder();//将str置空
                //是数字的话要判断多位数，需要循环拼接多位数
                while (index <s.length() && (c=s.charAt(index))>=48 && (c=s.charAt(index))<=57){
                    str.append(c);
                    index++;
                }
                list.add(str.toString());
            }
        }
        return list;
    }

    /**
     * 把一个中缀表达式list转为一个后缀表达式list
     * 1+((2+3)*4)-5
     * @return
     */
    public static List<String> toSufixExpressionList(List<String> infixExpressionList) {
        var s1 = new Stack<String>();//此栈用于放操作符
        var s2 = new ArrayList<String>();//次list用于放中间结果   这里用list，到时候就不用反转了
        String str;//遍历出来的元素
        for (String s : infixExpressionList) {
            str = s;
            //如果是操作符，就需要进行下一步判断
            if (isOper(str)) {
                //如果操作栈是空或者栈顶的数据是(，就直接入栈
                if (s1.isEmpty() || s1.peek().equals("(")) {
                    s1.push(str);
                }
                //FIXME 否则就需要和栈顶的操作符比较优先级
                //如果str的优先级比栈顶的高就把str压入栈中，
                else if (level(s1.peek()) < level(str)) {
                    s1.push(str);
                } else {
                    //否则就把s1中栈顶的运算符弹出压入s2，直到s1栈顶操作符的优先级<=str的优先级
                    while (s1.size() != 0 && level(s1.peek()) <= level(str)) {
                        s2.add(s1.pop());
                    }
                    //再把str压入s1符号栈中
                    s1.add(str);
                }
            }
            //如果是(,直接入操作栈
            else if (str.equals("(")) {
                s1.push(str);
                //如果是) ,则依次弹出s1栈顶的运算符，知道遇到(为止，然后将这一对括号去除
            } else if (str.equals(")")) {
                //遍历s1 把弹出的运算符放到s2中
                while (!s1.peek().equals("(")) {
                    String n = s1.pop();
                    s2.add(n);
                }
                //循环完之后此时栈顶的元素是(，也需要弹出去
                s1.pop();
                //如果是数字 ,直接入数栈
            } else if (str.matches("\\d+")) {
                s2.add(str);
            } else throw new RuntimeException("数据格式不正确");
        }
        while (s1.size() != 0) {
            s2.add(s1.pop());
        }
        return s2;
    }

    /**
     * 判断是不是操作符
     * @param str
     * @return boolean
     */
    public static boolean isOper(String str){
        return str.equals("*") || str.equals("+") || str.equals("/") || str.equals("-");
    }

    /**
     * 判断符号的优先级
     * @param val
     * @return
     */
    public static int level(String val) {
        if (val.equals("*") || val.equals("/")) {
            return 1;
        }else if (val.equals("+") || val.equals("-")){
            return 0;
        } else return 0;
    }
}
